USACO 2024 February Contest, Bronze

[USACO24FEB] 回文数游戏 （Palindrome Game B ）

题目描述

Bessie 和 Elsie 正在使用一堆初始时共 $S$ 个石子（$1\le S<{10}^{{10}^5}$）进行一个游戏。两头奶牛依次行动，Bessie 先行动。当轮到一头奶牛行动时，她必须从堆中取走 $x$ 个石子，其中 $x$ 是该奶牛选定的任意正整数回文数。如果当一头奶牛的回合开始时石子堆是空的，那么这头奶牛就输了。

定义：一个正整数如果从前向后和从后向前读相同，则该数为回文数；回文数的例子有 $1$，$121$ 和 $9009$。数不允许有前导零；例如，$990$ 不是回文数。

有 $T$（$1\le T\le 10$）个独立的测试用例。对于每一个测试用例，输出如果两头奶牛都采取最优策略，谁会赢得游戏。

输入格式

输入的第一行包含 $T$，为测试用例的数量。以下 $T$ 行为测试用例，每个测试用例一行。

每个测试用例均由一个整数 $S$ 指定。

输出格式

对于每一个测试用例输出一行，如果 Bessie 在最优策略下可以从一堆 $S$ 个石子的石子堆开始赢得游戏，则输出 B，否则输出 E。

样例 #1

样例输入 #1

3
8
10
12

样例输出 #1

B
E
B

提示

样例解释

对于第一个测试用例，Bessie 可以在第一次行动中取走所有石子，因为 $8$ 是回文数，使她获胜。

对于第二个测试用例，$10$ 不是回文数，因此 Bessie 无法在第一次行动中取走所有石子。无论 Bessie 第一回合取走多少石子，Elsie 总能在第二回合取走所有余下的石子，使她获胜。

对于第三个测试用例，可以证明在最优策略下 Bessie 可以获胜。

测试点性质

• 测试点 $2-4$：$S<100$。
• 测试点 $5-7$：$S<{10}^6$。
• 测试点 $8-10$：$S<{10}^9$。
• 测试点 $11-13$：没有额外限制。

参考答案

/*
博弈论。
列举一下回文数可以发现从 1 到 9 都是回文数，并且所有整十的数都不是回文数，因此只要剩下整十的石子数量，
就不能一次性取完，且还剩下的石子数量不为整十，所以对方便可以取完剩下数量的个位的数量，再留下整十的石子。
总结一下，只要石子的数量是整十的数，那么后手赢。反之，先手赢。
题解：https://www.luogu.com.cn/problem/solution/P10187
*/
#include"iostream"
#include"algorithm"
using namespace std;
int main(){
	int t;
	cin >> t;
	while(t--){
		string s;
		cin >> s;
		cout << ((s[s.size() -1] == '0') ? "E" : "B")<< endl;
	}
	return 0;
}

[USACO24FEB] Milk Exchange B

题目描述

Farmer John 的 $N$（$1\le N\le 2\cdot {10}^5$）头奶牛排成一圈，使得对于 $1,2,\dots ,N-1$ 中的每个 $i$，奶牛 $i$ 右边的奶牛是奶牛 $i+1$，而奶牛 $N$ 右边的奶牛是奶牛 $1$。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\le a_i\le {10}^9$）升的桶。所有桶初始时都是满的。

每一分钟，奶牛都会根据一个字符串 $s_1{s}_2\dots s_N$ 传递牛奶，该字符串仅由字符 L 和 R 组成。当第 $i$ 头奶牛至少有 $1$ 升牛奶时，如果 $s_i=\mathtt{\text{L}}$，她会将 $1$ 升牛奶传递给她左边的奶牛，如果 $s_i=\mathtt{\text{R}}$ 则传递给右边的奶牛。所有交换同时发生（即，如果一头奶牛的桶是满的，送出一升牛奶，但也收到一升，则她的牛奶量保持不变）。如果此时一头奶牛的牛奶量超过 $a_i$，则多余的牛奶会损失。

FJ 想要知道：经过 $M$ 分钟（$1\le M\le {10}^9$）后，所有奶牛总共还余下多少牛奶？

输入格式

输入的第一行包含 $N$ 和 $M$。

第二行包含一个字符串 $s_1{s}_2\dots s_N$，仅由字符 L 或 R 组成，表示每头奶牛传递牛奶的方向。

第三行包含整数 $a_1,a_2,\dots ,a_N$，为每个桶的容量。

输出格式

输出一个整数，为 $M$ 分钟后所有奶牛总共余下的牛奶量。

注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 long long）。

样例 #1

样例输入 #1

3 1
RRL
1 1 1

样例输出 #1

2

样例 #2

样例输入 #2

5 20
LLLLL
3 3 2 3 3

样例输出 #2

14

样例 #3

样例输入 #3

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4

样例输出 #3

38

提示

样例解释 1

奶牛 $2$ 和 $3$ 互相传递一升牛奶，因此她们的牛奶得以保留。当奶牛 $1$ 将牛奶传递给奶牛 $2$ 时，奶牛 $2$ 的桶会溢出，从而一分钟后损失了一升牛奶。

样例解释 2

每头奶牛都将一升牛奶传递给左边的奶牛，并从右边的奶牛那里获得一升牛奶，因此无论经过多长时间所有牛奶都会被保留下来。

样例解释 3

初始时，共有 $51$ 升牛奶。$5$ 分钟后，奶牛 $3$，$6$ 和 $7$ 将分别损失 $5$，$3$ 和 $5$ 升牛奶。因此，总共还剩下 $38$ 升牛奶。

测试点性质

• 测试点 $4-8$：$N,M\le 1000$。
• 测试点 $9-16$：没有额外限制。

参考答案

/*
观察题目，发现  倒入右边桶内， 倒入左边桶内，那如果当序列中出现了 ，就代表左边奶牛会给右边 ，右边奶牛会给左边 ，就代表这两个奶牛的瓶子一直保持着满瓶的状态，如果一旦外面有牛奶倒入，就会使瓶子满杯而产生总量损失，也只有这种情况会产生损失。外面有任何牛奶倒入就代表：左边临近的奶牛字符为  ，后边临近的奶牛字符为 。这就说明左/右一定会浪费牛奶，浪费牛奶数应为 ，因为倒牛奶最多有  轮，每轮只能给予一升牛奶， 便是最大值了，但如果奶牛已没有奶了，便无法给予。
我们会发现中间有一个 ，而左边是 4 个 ，这会引发一个奇妙的现象：最左边的  每轮给予下一个  一升，下一个  会给予再下一个  一升，引发了一个接力，直到将牛奶给予了  。出现了这个“接力”现象，计算浪费牛奶数就有亿点儿困难了，我们可以发现最后一个奶牛会经过接力持续给予牛奶，当没有牛奶时，就需要倒数第二个奶牛给予牛奶；当倒数第二个奶牛没有牛奶时，就需要倒数第三个奶牛给予牛奶……以此类推。根据这个现象，我们可以找到解决方法：从  处往左开始遍历，要求  不断开，则每一个就是 。其实就是将附近的  奶牛所持有的牛奶数累加，最大值不超过 ，找出一共可以给予  多少升牛奶（也就是损失了多少牛奶）。 与以上做法同理，只不过换了一个遍历方向。
综上所述，我们需要找到每个 ，被找到给  提供牛奶的奶牛，计算损失数，把所有损失数从总牛奶数减去，即为答案。
特别要提醒的是：第一只奶牛与第  只奶牛是连起来的，在遍历和寻找  请注意这一点。
题解：https://blog.csdn.net/a134679111111/article/details/136157130
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 1;
int n, m, res, a[N];
char c[N];
signed main(){
	scanf("%lld%lld%s", &n, &m, c);
	for(int i = 1;i <= n; i++){
		scanf("%lld", &a[i]);
		res += a[i];						//计算总牛奶值 
	}
	if(c[0] == 'L' && c[n - 1] == 'R')		//第一个与第 n 个形成 RL
		c[0] = ' ', c[n - 1] = ' ';
	for(int i = 1;i < n; i++)
		if(c[i - 1] == 'R' && c[i] == 'L')	//i-1 与 i 形成 RL
			c[i - 1] = ' ', c[i] = ' ';		//用空格代替，以记录 
	for(int i = 0;i < n; i++){
		int suma = 0, sumb = 0;				//suma 记录左边相连的奶牛给予牛奶的数量，sumb 则是记录右边的 
		int l = i - 1;
		if(l < 0)
			l = n - 1;
		if(c[l] != ' ' || c[i] != ' ')
			continue ;
		bool flag = false;
		for(int j = l - 1;j >= 0 && !flag; j--){
			if(c[j] == 'R')					//是否相连 
				suma = min(suma + a[j + 1], m);
			else
				flag = true;
		}
		if(!flag){							//如果持续相连直到第一个，那就从第 n 个往前检查是否还有相连 
			for(int j = n - 1;j >= 0 && !flag; j--){
				if(c[j] == 'R')
					suma = min(suma + a[j + 1], m);
				else
					flag = true;
			}
		}
		flag = false;						//以下同 suma 
		for(int j = i + 1;j < n && !flag; j++){
			if(c[j] == 'L')
				sumb = min(sumb + a[j + 1], m);
			else
				flag = true;
		}
		if(!flag){
			for(int j = 0;j < n && !flag; j++){
				if(c[j] == 'L')
					sumb = min(sumb + a[j + 1], m);
				else
					flag = true;
			}
		}
		res -= suma + sumb;					//从总牛奶数减去此 RL 损失数
	}
	printf("%lld", res);
	return 0;
}

[USACO24FEB] Maximizing Productivity B

题目描述

Farmer John 有 $N$（$1\le N\le 2\cdot {10}^5$）个农场，编号为 $1$ 到 $N$。已知 FJ 会在时刻 $c_i$ 关闭农场 $i$。Bessie 在时刻 $S$ 起床，她希望在农场关闭前访问尽可能多的农场，从而最大限度地提高她这一天的生产力。她计划在时刻 $t_i+S$ 访问农场 $i$。Bessie 必须于严格早于 Farmer John 关闭农场的时刻抵达农场才能成功进行访问。

Bessie 有 $Q$（$1\le Q\le 2\cdot {10}^5$）个询问。对于每个询问，她会给你两个整数 $S$ 和 $V$。对于每个询问，输出当 Bessie 在时刻 $S$ 起床是否可以访问至少 $V$ 个农场。

输入格式

输入的第一行包含 $N$ 和 $Q$。

第二行包含 $c_1,c_2,c_3\dots c_N$（$1\le c_i\le {10}^6$）。

第三行包含 $t_1,t_2,t_3\dots t_N$（$1\le t_i\le {10}^6$）。

以下 $Q$ 行，每行包含两个整数 $V$（$1\le V\le N$）和 $S$（$1\le S\le {10}^6$）。

输出格式

对 $Q$ 个询问的每一个输出一行，输出 YES（是）或 NO（否）。

样例 #1

样例输入 #1

5 5
3 5 7 9 12
4 2 3 3 8
1 5
1 6
3 3
4 2
5 1

样例输出 #1

YES
NO
YES
YES
NO

提示

样例解释

对于第一个询问，Bessie 将在时间 $t=[9,7,8,8,13]$ 访问农场， 因此她在 FJ 关闭农场之前能准时访问到的只有农场 $4$。

对于第二个询问，Bessie 将无法准时访问到任何农场。

对于第三个询问，Bessie 将可以准时访问到农场 $3,4,5$。

对于第四个和第五个询问，Bessie 将能够准时访问除第一个农场之外的所有农场。

测试点性质

• 测试点 $2-4$：$N,Q\le {10}^3$。
• 测试点 $5-9$：$c_i,t_i\le 20$。
• 测试点 $10-17$：没有额外限制。

参考答案

#include"iostream"
#include"algorithm"
using namespace std;
int a[200010];
int main(){
	int i,j,k,n,q;
	int v,s;
	cin>>n>>q;
	for(i=1;i<=n;i++){
		cin>>a[i];
	}
	for(i=1;i<=n;i++){
		cin>>j;
		a[i]-=j;
	}
//	for(i=1;i<=n;i++){
//		cout<<a[i]<<" ";
//	}
//	cout<<endl;
	sort(a+1,a+n+1);
	while(q--){
		cin>>v>>s;
		cout<<(a[n-v+1]>s ? "YES" : "NO")<<endl;
	}
	return 0;
}